package com.sheng.leetcode.year2022.month05.day20;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/05/20
 *
 * 436. 寻找右区间
 *
 * 给你一个区间数组 intervals ，其中 intervals[i] = [starti, endi] ，且每个 starti 都 不同 。
 * 区间 i 的 右侧区间 可以记作区间 j ，并满足 startj >= endi ，且 startj 最小化 。
 * 返回一个由每个区间 i 的 右侧区间 的最小起始位置组成的数组。如果某个区间 i 不存在对应的 右侧区间 ，则下标 i 处的值设为 -1 。
 *  
 * 示例 1：
 *
 * 输入：intervals = [[1,2]]
 * 输出：[-1]
 * 解释：集合中只有一个区间，所以输出-1。
 * 示例 2：
 *
 * 输入：intervals = [[3,4],[2,3],[1,2]]
 * 输出：[-1,0,1]
 * 解释：对于 [3,4] ，没有满足条件的“右侧”区间。
 * 对于 [2,3] ，区间[3,4]具有最小的“右”起点;
 * 对于 [1,2] ，区间[2,3]具有最小的“右”起点。
 * 示例 3：
 *
 * 输入：intervals = [[1,4],[2,3],[3,4]]
 * 输出：[-1,2,-1]
 * 解释：对于区间 [1,4] 和 [3,4] ，没有满足条件的“右侧”区间。
 * 对于 [2,3] ，区间 [3,4] 有最小的“右”起点。
 *
 * 提示：
 *
 * 1 <= intervals.length <= 2 * 104
 * intervals[i].length == 2
 * -106 <= starti <= endi <= 106
 * 每个间隔的起点都 不相同
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/find-right-interval
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0436 {

    @Test
    public void test01(){
//        int[][] intervals = {{1,2}};
//        int[][] intervals = {{3,4},{2,3},{1,2}};
//        int[][] intervals = {{1,4},{2,3},{3,4}};
        //可以选择当前数组为右侧区间
        int[][] intervals = {{1,1},{3,4}};
        int[] ints = new Solution().findRightInterval(intervals);
        for (int i = 0; i < ints.length; i++) {
            System.out.println(ints[i]);
        }
    }

}
class Solution {
    public int[] findRightInterval(int[][] intervals) {
        //创建返回的数组
        int[] ints = new int[intervals.length];
        //循环
        for (int i = 0; i < intervals.length; i++) {
            int[] interval = intervals[i];
            int j = 0;
            int n = -1;
            while (j < intervals.length) {
                //满足条件  startj >= endi
                if (intervals[j][0] >= interval[1]) {
                    //如果当前结点的start比上一个结点的start小，则替换
                    if (n == -1 || intervals[n][0] > intervals[j][0]) {
                        n = j;
                    }
                }
                j++;
            }
            //此时的n，即是当前数组满足条件的右侧区间的坐标
            ints[i] = n;
        }
        return ints;
    }
}
